#include <bits/stdc++.h>

using namespace std;

// 最小区间
// 你有k个非递减排列的整数列表
// 找到一个最小区间，使得k个列表中的每个列表至少有一个数包含在其中
// 测试链接 : https://leetcode.cn/problems/smallest-range-covering-elements-from-k-lists/

class Solution 
{
public:
    struct Node 
    {
        int v; // 值
        int i; // 当前值来自哪个数组
        int j; // 当前值来自i号数组的什么位置
        
        Node(int a = 0, int b = 0, int c = 0) : v(a), i(b), j(c) {}
        
        bool operator<(const Node& other) const 
        {
            return v != other.v ? (v < other.v) : (i < other.i);
        }
    };

	// 时间复杂度O(n*logk)
	// n是数字总数，k是数组数量
    vector<int> smallestRange(vector<vector<int>>& nums) 
    {
        int k = nums.size();
        // 根据值排序
        // 为什么排序的时候i要参与
        // 因为有序表中比较相等的样本只会保留一个
        // 为了值一样的元素都保留，于是i要参与排序
        // 在有序表中的所有元素i必然都不同
        // set 默认是使用小于号来比较的，其中序遍历的结果是升序的
        // 因此 Node 可以进行小于号的重载
        set<Node> s; 
        // 没有必要以列表中没有出现过的数字做开头和结尾
        for (int i = 0; i < k; i++) s.insert(Node(nums[i][0], i, 0));
        int r = INT_MAX; // 记录最窄区间的宽度
        int a = 0; // 记录最窄区间的开头
        int b = 0; // 记录最窄区间的结尾
        Node mx, mn;
        // 一定要凑齐 k 个元素才进行，因为这 k 个元素都是来自不同的组
        while (s.size() == k) 
        {
            mx = *s.rbegin(); // 在有序表中，值最大的记录
            mn = *s.begin(); // 在有序表中，值最小的记录，并弹出
            s.erase(mn);
            if (mx.v - mn.v < r) // 宽度变小了
            {
                r = mx.v - mn.v;
                a = mn.v;
                b = mx.v;
            }
            // 如果当前最小数的所在组有下一个数，那么就让其进入 set 中
            // 如果没有下一个数，其实就可以跳出循环了，因为 set 中的元
            // 素将不够 k 个
            if (mn.j + 1 < nums[mn.i].size()) 
            {
                s.insert(Node(nums[mn.i][mn.j + 1], mn.i, mn.j + 1));
            }
        }
        return {a, b};
    }
};